The present invention is related to the access and storage of data having implicit hierarchies. An example of data that may be hierarchically stored and accessed is directory information based on the Lightweight Directory Access Protocol (“LDAP”). LDAP is a directory protocol that was developed at the University of Michigan, originally as a front end to access directory systems organized under the X.500 standard for open electronic directories (which was originally promulgated by the Comite Consultatif International de telephone et Telegraphe “CCITT” in 1988). Standalone LDAP server implementations are now commonly available to store and maintain directory information.
LDAP directory systems are normally organized in a structure having entries (i.e., objects) organized in the form of a tree, which is referred to as a directory information tree (“DIT”). A unique name or ID (which is commonly called a “distinguished name” or “DN”) identifies each LDAP entry in the DIT. An LDAP entry is a collection of one or more entry attributes. Each entry attribute has a “type” and one or more “values.” Each entry belongs to one or more object classes.
If structured properly, a DIT represents an explicit hierarchy. Such a DIT only represent a single hierarchical relationship among directory entries. However, each entry in the DIT has several attributes and values of some of these attributes may represent additional hierarchical relationships among these directory entries built on different criterias and thus creating an implicit hierarchies which are not reflected in the DIT structure in which these entries exist. For example, an enterprise may choose to represent its users based on their geographical locations. This enterprise may also have an organizational structure or organizational reporting structure that is not geographically based, and which is represented as attribute data. In such a case, the geographically-based DIT structure does not show the organizational hierarchy. The organization structure which is represented as an attribute values of these entries thus forms an implicit hierarchy in the LDAP data.
For example, consider the DIT 151a of FIG. 1A, which is hierarchically organized based upon geographic location. Entry 152 is the top most level of DIT 151a and identifies the DIT portion 151a as pertaining to an organization “Foo” (o=Foo). Entry 152 is the “parent” entry for two “child” entries 153 and 155 directly beneath it in DIT 151a. Each of these entries corresponds to a geographical location. Specifically, entry 153 corresponds to the geographic location “c=US” and entry 155 corresponds to the geographic location “c=Japan”.
The entries for each user/person in the Foo organization are located as child entries to either entry 153 or 155, depending upon their specific geographic location. Here, users “Tom” and “Harry” are located in the US; therefore, the individual entries 157 and 159 for these users are located beneath entry 153 (c=US) in DIT 151a. User “Joe” is located in Japan; therefore, the individual entry 161 for this user is located beneath the entry 155 (c=Japan) in DIT 151a. The distinguished name (“DN”) for cn=Tom would therefore be “cn=Tom, c=US, o=Foo” and the distinguished name for cn=Harry would be “cn=Harry, c=US, o=Foo”. The distinguished name for Joe is “cn=Joe, c=Japan, o=Foo”.
Based upon the organization structure for their enterprise, each person also has a manager within the organization Foo. The organizational structure for this enterprise is shown in FIG. 1B. Here, Harry is the manager of Tom, and Tom is the manager of Joe. Assume that the manager for each individual is listed as an attribute associated with the entry for that individual, as shown in FIG. 1A. The explicit hierarchy of DIT 151a of FIG. 1A does not correspond or show the implied hierarchy of FIG. 1B, even though the manager attribute information for the entries 157, 159, and 161 correspond to this implied hierarchy.
The same scenario applies to Group objects as well. “Group A” can be a member of “Group B”. A user who is a member of “Group A” is also a member of “Group B”. The membership of“Group A” into “Group B” represents a implicit hierarchy. However, the same is not reflected in the place that these groups are created in the DIT.
To illustrate, consider the DIT 151b of FIG. 2A, which shows an additional two groups Group A and Group B, which are identified as entries 163 and 165, respectively. As before, DIT 151b is organized along geographical boundaries. Based upon the listed attributes for the entries in DIT 151b, Group A is a member of Group B (entry 165). User Harry is a member of Group B (entry 159). Users Tom and Joe are members of Group A (entries 157 and 161). Therefore, the memberships of the Groups are organized in the implied hierarchy shown in FIG. 2B and are not explicitly shown in the DIT 151b. 
Directory protocols, such as the LDAP Protocol, do not natively have provisions for clients to queries and resolve implicit hierarchies. This type of functionality is becoming more and more important as products start using such directories for purposes like building a Email distribution list or using groups for application authorizations where the assertion used for setting up objects like distribution list are hierarchical and the client needs to resolve the entire hierarchy. The current limitations in the protocols make it very inefficient for clients to query such implicit hierarchical data. For example, a client cannot ask for the “mail” attribute of all users under a particular manager and get mail attributes for all its direct and in-direct reports until the DIT structure represents such a hierarchy, but then the DIT structure can represent only one hierarchy and hence results in limitations when attempting to query for an implicit hierarchy. The existing LDAP Search semantics allow one to get “mail” attributes for direct reports only. The client then has to query for the direct reports of all entries returned and continue this recursively till all the entries have been examined. This results in performing several queries on the LDAP server. This certainly is not a scalable solution and has performance implications.
The present invention provides a method, system, and article of manufacture for querying an implicit hierarchy. According to one embodiment of the invention, implicit hierarchies can be queried by accessing the relevant catalog tables for the attribute relevant to the query. Each identified entry in the relevant catalog table is followed through its implied hierarchical chains until all relevant entries have been identified. The catalog table containing the normalized form of the DN can be consulted to identify the entry identifier for each entry corresponding to implicit hierarchy being queried, which can be searched in the appropriate catalog table to search the chain of entries for the implied hierarchy. In an embodiment, one or more templates may be used to generate a query language statement to perform the query upon the implicit hierarchy.
Further details of aspects, objects, and advantages of the invention are described below in the detailed description, drawings, and claims. Both the foregoing general description and the following detailed description are exemplary and explanatory in nature, and serve to explain the principles of the invention.